package com.chenxys.algorithm.newbie;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <p>
 *      使用双向链表实现双向队列
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.newbie
 * @date 12/28/23 11:59 PM
 * @Copyright ©
 */
public class DeQueueByDoubleList {

    public static class Node<V> {
        // 当前节点值
        private V value;
        // 当前节点指向的上一个节点
        public Node<V> last;
        // 当前节点指向的下一个节点
        public Node<V> next;

        public Node(V value) {
            this.value = value;
            this.last = null;
            this.next = null;
        }
    }

    public static class MyDeQueue<V> {
        // 队列头指针,包含上一个节点地址和下一个节点地址
        private Node<V> head;
        // 队列尾指针,包含上一个节点地址和下一个节点地址
        private Node<V> tail;
        // 队列长度
        private int size;

        public MyDeQueue() {
            this.head = null;
            this.tail = null;
            this.size = 0;
        }

        // 判断当前队列是否为空
        public boolean isEmpty() {
            return size == 0;
        }

        // 获取当前队列长度
        public int size() {
            return size;
        }

        /**
         * <p>
         *     将一个元素放到队列头
         * </p>
         * @param value 待插入的元素
         */
        public void pushHead(V value) {
            // 保存当前元素值
            Node<V> cur = new Node<>(value);
            // 判断当前队列是否为空
            if (head == null) {
                // 为空，当前节点既是头,又是尾
                head = cur;
                tail = cur;
            } else {
                // 不为空 将当前元素的下一个节点指向队列头
                cur.next = head;
                // 将队列头的上一个节点指向当前节点
                head.last = cur;
                // 将当前节点赋值为队列头
                head = cur;
            }
            // 队列长度+1
            size++;
        }

        /**
         * <p>
         *     将元素加入到队列尾
         * </p>
         * @param value 待进入队列的元素
         */
        public void pushTail(V value) {
            // 新建节点保存当前元素
            Node<V> cur = new Node<>(value);
            // 如果当前队列为空
            if (head == null) {
                // 将队列头指向当前节点
                head = cur;
                // 将队列尾也指向当前节点
                tail = cur;
            } else {
                // 将队列尾的下一个节点指向当前节点
                tail.next = cur;
                // 将当前节点的上一个节点指向队列尾节点
                cur.last = tail;
                // 将队列尾节点赋值当前节点
                tail = cur;
            }
            // 队列长度+1
            size++;
        }

        /**
         * <p>
         *     弹出队列头节点的值
         * </p>
         * @return 头节点的值
         */
        public V pollHead(){
            V ans = null;
            // 如果队列为空,直接返回空
            if (head == null) return ans;
            // 队列不为空, 队列长度-1
            size--;
            ans = head.value;
            // 如果队列中只有一个元素,全指向空
            if (head == tail){
                head = null;
                tail = null;
            } else {
                // 不是一个元素,头指针指向当前头的下一个节点
                head = head.next;
                // 头指针上一个节点指向空
                head.last = null;
            }
            return ans;
        }

        /**
         * <p>
         *     弹出队列尾节点的值
         * </p>
         * @return 尾节点的值
         */
        public V pollTail(){
            V ans = null;
            // 如果队列为空,直接返回空
            if (head == null) return ans;
            // 队列不为空, 队列长度-1
            size--;
            // 弹出当前尾指针指向节点的值
            ans = tail.value;
            // 只有一个元素,则把头尾指针都指向空
            if (head == tail){
                head = null;
                tail = null;
            } else {
                // 不止一个元素,尾指针指向当前尾指针指向节点的上一个节点
                tail = tail.last;
                // 尾指针的下一个节点指向空
                tail.next = null;
            }
            return ans;
        }

        /**
         * <p>
         *     返回当前头节点的值,但不删除
         * </p>
         * @return 当前头节点的值
         */
        public V peekHead() {
            V ans = null;
            // 头指针不为空
            if (head != null) ans = head.value;
            return ans;
        }

        /**
         * <p>
         *     返回当前尾节点的值,但不删除
         * </p>
         * @return 当前尾节点的值
         */
        public V peekTail() {
            V ans = null;
            // 尾指针不为空
            if (tail != null) ans = tail.value;
            return ans;
        }
    }

    public static void main(String[] args) {
        MyDeQueue<Integer> MyDeQueue = new MyDeQueue<>();
        Deque<Integer> test = new LinkedList<>();
        int testTime = 5000000;
        int maxValue = 200000000;
        System.out.println("Test Begin！");
        for (int i = 0; i < testTime; i++) {
            if (MyDeQueue.isEmpty() != test.isEmpty()) {
                System.out.println("Oops!");
            }
            if (MyDeQueue.size() != test.size()) {
                System.out.println("Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                if (Math.random() < 0.5) {
                    MyDeQueue.pushHead(num);
                    test.addFirst(num);
                } else {
                    MyDeQueue.pushTail(num);
                    test.addLast(num);
                }
            } else if (decide < 0.66) {
                if (!MyDeQueue.isEmpty()) {
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random() < 0.5) {
                        num1 = MyDeQueue.pollHead();
                        num2 = test.pollFirst();
                    } else {
                        num1 = MyDeQueue.pollTail();
                        num2 = test.pollLast();
                    }
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            } else {
                if (!MyDeQueue.isEmpty()) {
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random() < 0.5) {
                        num1 = MyDeQueue.peekHead();
                        num2 = test.peekFirst();
                    } else {
                        num1 = MyDeQueue.peekTail();
                        num2 = test.peekLast();
                    }
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            }
        }
        if (MyDeQueue.size() != test.size()) {
            System.out.println("Oops!");
        }
        while (!MyDeQueue.isEmpty()) {
            int num1 = MyDeQueue.pollHead();
            int num2 = test.pollFirst();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("Test Finish！");
    }
}
